/*
 * @lc app=leetcode.cn id=61 lang=cpp
 *
 * [61] 旋转链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
 public:
  /*
  ListNode* rotateRight(ListNode* head, int k) {
      if(head==NULL) return NULL;
      long long n=0;
      while(head) n++;
      k%=n;

      // 开始旋转
      ListNode* first=head;
      ListNode* second=head;

      while(k--) first=first->next;
      while(first->next)
      {
        first=first->next;
        second=second->next;
      }
      second->next->next->next=head;
      head=second->next;
      second->next=NULL;

      return head;

  }*/

  ListNode* rotateRight(ListNode* head, int k)
  {
    if (!head) return NULL;

    int n = 0;
    for (auto p = head; p; p = p->next) n++;
    k %= n;
    auto first = head, second = head;
    while (k--) first = first->next;
    while (first->next)
    {
      first = first->next;
      second = second->next;
    }

    // second->next->next->next=head;
    first->next = head;
    head = second->next;
    second->next = NULL;

    return head;
  }
};
// @lc code=end
